Large, high-capacity data communication networks, such as the Internet, are typically based on packet-switched techniques. In such techniques data to be communicated are divided into blocks each of which is combined with a header to form a data packet. The header includes, for example, information identifying the particular communications transaction to which the packet relates, and routing information identifying the sender and intended recipient of the data. Each packet is transmitted through the network between packet switching devices, such as hubs and routers, which examine the packet's header and use the routing information, in conjunction with data about the current operating status of the network, to choose a transmission path along which to route the packet towards its final destination.
As the demand for new and better quality data transmission increases, so does the need for faster yet more flexible packet switching devices. One technique used within packet switches for examining packet headers and making routing decisions relies upon the use of data structures often referred to as decision trees (though more formally described as directed acyclic graphs). Current implementations of decision trees suffer from various disadvantages. For example, typically a complete tree is developed in a single operation from a set of rules defining how packets are to be routed; thus even a single, trivial change to the rules involves generation of a complete new tree. If this tree is to replace an existing tree in a packet switch, the switch must be temporarily disabled (or at the very least incoming packets must be buffered) while the tree substitution takes place, in order to avoid the substitution affecting a packet for which routing decisions using the tree are already in progress. This both reduces the throughput of the packet switch, and increases its complexity and cost. Alternatively, two copies of the entire decision tree may be maintained, an active one for routing packets, and an inactive one which may safely be modified; when the modifications are complete, the active tree is made inactive and vice versa. Although such "double-buffering" avoids reducing the throughput of the switch, it involves expensive duplication of high-speed memory typically used to store decision trees.
It would be highly desirable to have a decision tree system which permitted incremental changes to be made to the decision tree in response to changes in the associated routing rules. It is also desirable that such changes be made without interrupting operation of the packet switch more than momentarily, and without any need to buffer incoming packets. It is an object of this invention to provide a method which facilitates the use of decision trees.